package com.ian.offer;

import com.ian.linked.TreeNode;
import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangyaowen
 * @date 2021/2/23 10:11 下午
 */

/**
 *
 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。



 例如:
 给定二叉树: [3,9,20,null,null,15,7],

 3
 / \
 9  20
 /  \
 15   7
 返回其层次遍历结果：

 [
 [3],
 [9,20],
 [15,7]
 ]


 提示：

 节点总数 <= 1000
 */
public class LevelOrder {

    public List<List<Integer>> levelOrder(TreeNode root) {

         List<List<Integer>> list  = new ArrayList<>();
         Queue<TreeNode> queue  = new ArrayDeque();

         if (root ==null){
             return  list;
         }
         queue.add(root);

         while(!queue.isEmpty()){

             List<Integer> temp = new ArrayList<>();

             for (int i = queue.size(); i >0; i--) {

                  TreeNode node =  queue.poll();

                  if (node.left !=null) queue.add(node.left);

                  if (node.right!= null) queue.add(node.right);

                  temp.add(node.val);
             }

             list.add(temp);

         }

         return  list;
    }
}
